#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 572. 另一棵树的子树
// https://leetcode.cn/problems/subtree-of-another-tree/description/

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    vector<int> morris(TreeNode *root)
    {
        vector<int> ans;
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        while (cur != nullptr)
        {
            if (cur->left == nullptr)
            {
                ans.push_back(cur->val);
                ans.push_back(INT_MAX);
                cur = cur->right;
                continue;
            }
            pre = cur->left;
            while (pre->right != nullptr && pre->right != cur)
            {
                pre = pre->right;
            }
            if (pre->right == nullptr)
            {
                ans.push_back(cur->val);
                pre->right = cur;
                cur = cur->left;
            }
            else
            {
                ans.push_back(INT_MAX);
                cur = cur->right;
                pre->right = nullptr;
            }
        }
        ans.push_back(INT_MAX);

        return ans;
    }
    vector<int> nextArr(vector<int> &sub)
    {
        int n = sub.size();
        vector<int> next(n, -1);
        if (n == 1)
        {
            return next;
        }
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < n)
        {
            if (sub[i - 1] == sub[cn])
            {
                next[i++] = ++cn;
            }
            else if (cn > 0)
            {
                cn = next[cn];
            }
            else
            {
                next[i++] = 0;
            }
        }
        return next;
    }
    bool KMP(vector<int> &root, vector<int> &sub)
    {
        vector<int> next = nextArr(sub);
        int x = 0;
        int y = 0;
        int n = root.size();
        int m = sub.size();
        while (x < n && y < m)
        {
            if (root[x] == sub[y])
            {
                x++;
                y++;
            }
            else if (y == 0)
            {
                x++;
            }
            else
            {
                y = next[y];
            }
        }
        return y == m;
    }
    bool isSubtree(TreeNode *root, TreeNode *subRoot)
    {
        vector<int> rootArr = morris(root);
        vector<int> subArr = morris(subRoot);

        return KMP(rootArr, subArr);
    }
};

int main()
{
    return 0;
}